Delete Every Alternate Node in a Cyclic Linked List

Interviewer: Let’s talk about linked lists again — but this time, let’s make it interesting. Imagine you’re given a circular linked list. Can you delete every alternate node from it?

Candidate: Sure! But before diving in, I’d like to confirm a few details about the problem.

Interviewer: Go ahead.

Candidate: So, when you say delete every alternate node, do we start deletion from the first node or the second? And since this is a cyclic list, does the deletion continue until we’re back at the head node again?

Interviewer: Excellent clarification. Yes, we start deleting from the second node. And since it’s a circular list, you’ll continue the deletion process until you come back to the head.

Candidate: Got it! So, essentially we’ll delete the 2nd, 4th, 6th... nodes, looping around in a circle until every alternate node is gone.

Understanding the Problem

Candidate: Let’s visualize this.

// Suppose we have a cyclic linked list: 1 → 2 → 3 → 4 → 5 → back to 1
// After deleting alternate nodes:
// Step 1: Delete 2 → List becomes 1 → 3 → 4 → 5 → back to 1
// Step 2: Delete 4 → List becomes 1 → 3 → 5 → back to 1
// Final Result: 1 → 3 → 5 → (circular)

Candidate: So the goal is to maintain the circular structure while skipping every second node in traversal.

Approach Discussion

Interviewer: So what’s your approach?

Candidate: My plan is simple:

• Start from the head node.
• While the list has more than one node, skip one node and delete the next.
• Since it’s circular, we stop when we come back to the head.

Candidate: The tricky part here is ensuring that after deleting a node, the links remain intact and the list still points back to the head correctly.

Pseudo-code

function deleteAlternateNodes(head):
    # Base case: If list is empty or has only one node
    if head == NULL or head.next == head:
        return head

    current = head

    # Loop until we reach back to head
    while current.next != head and current.next.next != head:
        temp = current.next          # node to be deleted
        current.next = temp.next     # skip deleted node
        free(temp)                       # free memory
        current = current.next       # move to next node

    # Handle last node deletion if list has even number of nodes
    if current.next != head:
        temp = current.next
        current.next = head
        free(temp)

    return head

Candidate: This ensures we delete every alternate node while preserving the circular connection.

Time & Space Complexity

• Time Complexity: O(N) — every node is visited once.
• Space Complexity: O(1) — constant extra space used.

Key Takeaways

• Clarify deletion pattern first. In cyclic lists, start point and stopping condition are crucial.
• Watch the loop condition. Always ensure you stop before the head is revisited, or you’ll end up in an infinite loop.
• Preserve circular linkage. After every deletion, check that the last node still points to head.
• Tip used: Pointer manipulation without extra space — classic test of linked list fundamentals.

Interviewer: Excellent. That’s exactly the clarity I was looking for. You maintained the cyclic property and handled edge cases cleanly.

Candidate: Thank you! I made sure to focus on pointer adjustment and termination conditions, as they are the most error-prone in circular structures.